1. Field of the Invention
The present invention concerns digital signal filtering, such as the transformation of a digital signal into frequency sub-band signals.
2. Description of Related Art
Many digital filtering methods and devices are known. Analysis filterings and corresponding digital signal synthesis filterings are considered here by way of example.
These filterings are generally subsystems integrated into coding and/or decoding systems. They often require a large amount of random access memory or buffer memory space, for storing the data in the course of processing.
However, in practice, the size of the memory means is often less than the size which would be necessary for storing an entire set of data, for example of a digital image.
The present invention firstly provides a method and a device for transforming a digital signal which optimise the buffer memory occupation of the data in the course of processing.
Since the size of the memory means is often less than the size which would be necessary for storing an entire set of data, it is therefore necessary to xe2x80x9ccutxe2x80x9d the signal into blocks and to process the blocks one after the other.
However, between an analysis and the corresponding synthesis of a signal, other processings, such as quantization or entropic coding, are generally applied to said signal. These processings, combined with processing by blocks, cause degradation in the reconstructed signal.
The present invention also provides a method and a device for transforming a digital signal which processes the signal by blocks, whilst limiting the degradation in the reconstructed signal, where other processings are applied to the signal between its transformation and its reconstruction.
The considered filterings are implemented by trellis filters. For practical reasons, it is often necessary to modify the theoretical calculations during implementation.
For example, these filterings often require a large amount of random access memory or buffer memory space, for storing the data in the course of processing. The data are then processed by blocks, as previously exposed.
However, it is known that processing by blocks causes degradation in the reconstructed signal.
The present invention also provides a method and device for transforming a digital signal which limits the degradation in the reconstructed signal.
The invention proposes a method of analysis filtering of an original digital signal including original samples representing physical quantities, original samples of the digital signal being transformed by successive calculation steps into high and low frequency output samples, any sample calculated at a given step being calculated by a predetermined function of original samples, and/or previously calculated samples, the samples being ordered in increasing rank,
characterised in that:
the signal is processed by successive series of samples, the calculations made on any series not taking into account the samples in a following series, and in that said any series terminates in a low-frequency sample.
The invention also proposes an analysis filtering method of an original digital signal including original samples representing physical quantities, comprising the following steps:
dividing the original signal in order to form plural series of samples,
filtering the original samples in a predetermined order and series by series, in order to generate at least one series of high and low-frequency samples,
wherein the end of said at least one series of high and low-frequency samples is a low-frequency sample.
According to the invention, the buffer memory space required for the filtering is reduced, because it is not necessary to store simultaneously all the samples in the buffer memory when being filtered series by series.
According to an other effect, as shown in FIG. 22a, where the end of a series is a high-frequency sample, it is impossible to utilise sample B when sample A is synthesized because sample B in next series has not been generated yet. As a result, a discontinuity between samples A and B is generated.
FIG. 22b where the end of a series is a low-frequency sample, when samples C and D are synthesized respectively, it is possible to use low-frequency sample in previous rank which is necessary for generating a new accurate low-frequency sample. Namely, the distortion is mainly controlled by low-frequency samples. Therefore, it is possible to refer low-frequency sample over the boundary to reduce the distortion. As a result, a discontinuity between samples C and D is not generated, so sample C will be used for the synthesis of D and E samples. This configuration considerably limits the degradations on bordering samples.
The invention also proposes a method of synthesis filtering of a digital signal including high and low-frequency interlaced samples obtained by applying the above analysis filtering method to original samples, wherein:
the signal is processed by successive series of samples in a predetermined order, and the end of the series is a low-frequency sample.
By such analysis method, the distortions on the synthesized signals, especially on borders of series, are cancelled. The synthesis then needs only small buffer memory and provides signal without any distortion.
The invention also proposes a method of synthesis filtering of a digital signal including high and low-frequency interlaced samples obtained by applying the above analysis filtering method to an original digital signal including samples representing physical qualities, samples being ordered by increasing rank,
characterised in that:
the signal is processed by successive series of samples, the calculations made on any series not taking into account the samples of a following series, and in that said any series terminates in a low-frequency sample.
In addition, the buffer memory space taken up by the data currently being processed is optimised, since the signal is processed by blocks. Thus complex filterings can be integrated into numerous appliances, without these requiring very large memories.
According to a preferred characteristic, on synthesis, each series of samples terminates after a last sample of a series determined at the time of an analysis filtering as defined above.
According to another preferred characteristic, both on analysis and on synthesis, said any series terminates in a low-frequency sample of the lowest resolution level. This configuration considerably limits the degradation in the reconstructed signal.
The invention also proposes a method of analysis filtering of an original digital signal including original samples representing physical quantities, original samples of the digital signal being transformed by successive calculation steps into high and low frequency output samples, any sample calculated at a given step being calculated by a predetermined function of original samples, and/or previously calculated samples, the samples being ordered in increasing rank,
characterised in that:
the signal is processed by first successive input blocks of samples, the calculations made on a first input block under consideration taking into account only the original or calculated samples belonging to the first input block under consideration,
the first input block under consideration and the first following input block overlap over a predetermined number of original samples.
According to preferred characteristics:
the start limit of the first input block under consideration is formed between a first original sample and a first output sample, passing successively from a previous sample to a following sample calculated according to the previous sample, the following sample having a rank equal to or greater than the previous sample,
the end limit of the first input block under consideration is formed between a second original sample and a second output sample, passing successfully from a previous sample to a following sample calculated according to the previous sample, the following sample having a rank equal to or lower than the previous sample,
the end limit of the first input block under consideration and the start limit of the first following input block are such that there is no compatibility sample having a rank strictly lower than the rank of the sample belonging to the start limit of this first following input block and to the same row as the compatibility sample, and at the same time a rank strictly greater than the rank of the sample belonging to the end limit of the first input block under consideration and to the same row as the compatibility sample.
By virtue of the invention, the buffer memory occupation of the data in the course of processing is optimised. Thus complex filterings can be integrated in many appliances, without requiring very large memories.
In addition, the inventors have found that the invention limits the degradations in the reconstructed signal. This is because chopping the signal to be processed in order to filter it, and then applying other processings to it, such as quantization or entropic coding, causes discontinuities in the signal which is subsequently reconstructed. These discontinuities are eliminated by virtue of the invention.
According to another characteristic, the method of analysis filtering, respectively the method of synthesis by successive input blocks of samples, is particularly efficient for two dimensional digital original signals in term of memory required and also avoids distortions generated by such signal division.
According to a preferred characteristic, first adjacent output blocks are formed, each first output block corresponding respectively to a first input block, the boundary between two first output blocks being situated between a third and a fourth output sample, the third output sample having a rank lower than that of the fourth output sample, the third and fourth samples being consecutive and chosen so that:
all the samples which have a rank less than or equal to the third output sample are original or calculated samples which are situated in one of the first input blocks,
all the samples which have a rank greater than or equal to the fourth output sample are original or calculated samples which are situated in another one of the first input blocks.
According to another preferred characteristic, two first successive input blocks overlap over a single original sample. Thus the memory occupation of the data currently being processed is minimal, since the overlap between blocks is minimal. Preferably, this original sample has the same rank as a low-frequency output sample. Thus the distortions in the reconstructed signal are minimal. The increase in coding efficiency from an overlap of 0 to an overlap over a single sample is very significant and noticeable, while it is much less for further increases in overlap size. Most of distortions of the reconstructed image are reduced in a particularly effective manner with the invention while a larger overlap does not provide effective improvement for distortions. In contradiction with the knowledge of a person skilled in the art, such distortion reduction is not linearly dependant of the amount of overlap samples.
The invention also concerns a method of synthesis filtering of a digital signal including high and low frequency interlaced samples obtained by applying the analysis filtering method according to the invention to an original digital signal including samples representing physical quantities, the samples being ordered in increasing rank, characterised in that:
the signal is processed by second successive input blocks of samples, the calculations performed on a second given input block taking into account only the samples belonging to the given input block,
the second input blocks are formed so that the calculations are adapted to the limits of the second input blocks in correspondence with the calculations made on analysis.
According to a preferred characteristic, the synthesis filtering method is such that second adjacent output blocks are formed, any second output block includes samples having the same ranks as the samples of a first output block used during the analysis filtering.
The invention also proposes a method of analysis filtering of an original digital signal including original samples representing physical quantities, original samples of the digital signal being transformed by successive calculation steps into high and low frequency output samples, the samples being ordered by increasing rank, any sample under consideration calculated at a given step being calculated by a predetermined function which makes it depend on several original samples, and/or previously calculated samples, one of them having the same rank as the sample under consideration,
characterised in that the calculation of at least one sample under consideration is modified in order to:
eliminate its dependence on at least one original sample and/or previously calculated sample having a different rank from the sample under consideration,
transfer the eliminated dependence to the original sample or previously calculated sample, having the same rank as the sample under consideration.
The invention applies notably to the case where the signal is processed by successive input blocks of samples, the calculation effected on a given block taking into account only the original or calculated samples belonging to the given input block.
By virtue of the invention, the degradation in the reconstructed signal is limited. This is because the normalization properties of the transformations effected are preserved with the invention.
In addition, the buffer memory occupation by the data in the course of processing is optimised, since the signal is processed by blocks. Thus complex filterings can be integrated in many apparatuses, without their requiring very large memories.
According to a preferred characteristic, the predetermined function is a predetermined linear combination of several original samples, and/or previously calculated samples, weighted by respective weighting coefficients,
previously calculated low-frequency samples on which there depend the sample from which the eliminated dependence issued and the sample to which the eliminated dependence is transferred are considered,
a total weight of the sample from which the eliminated dependence issued is calculated by setting to the value one the low-frequency samples previously calculated and calculating the value of this sample,
a total weight of the sample to which the eliminated dependence is transferred is calculated by setting to the value one the low-frequency samples previously calculated and calculating the value of this sample,
the weighting coefficient of the original sample or previously calculated sample, having the same rank as the sample under consideration, is modified by adding the product of the total weight of the sample from which the eliminated dependence issued and the weighting coefficient of this eliminated dependence, this product also being divided by the total weight of the sample to which the eliminated dependence is transferred.
This implementation entails calculations which are simple.
The invention also concerns a digital signal coding method which includes
the analysis filtering as defined above,
a quantization of the previously filtered samples, and
an entropic coding of the previously quantized samples.
According to this coding method, the signal is processed by successive series of samples, the calculations made on any series not taking into account the samples of a following series, and said any series terminates in a low-frequency sample.
The invention also concerns a method of decoding a digital signal coded according to the above coding method, including:
an entropic decoding of coded samples of the coded digital signal,
a dequantization of the previously decoded samples,
a synthesis filtering of the previously dequantized samples, as defined above.
According to the decoding method, the signal is processed by successive series of samples, the calculations made on any series not taking into account the samples of a following series, and said any series terminates in a low-frequency sample.
By virtue of the invention, the degradations in the reconstructed signal are limited.
According to preferred characteristics, the digital signal is an image signal and the original samples are rows or columns of the image. The invention-applies advantageously to an image signal, which generally requires a large amount of memory space. This memory space is reduced by virtue of the invention.
Correlatively, the invention proposes analysis filtering, synthesis filtering, coding and decoding devices integrating respectively the analysis and synthesis filtering, which have means of implementing the previously disclosed characteristics.
The invention also concerns a digital apparatus including the above device or means of implementing the above method. The advantages of the device and of the digital apparatus are identical to those previously disclosed.
The invention also concerns an information storage means, which can be read by a computer or by a microprocessor, integrated or not into the device, possibly removable, and stores a program implementing the filtering method.
The invention also concerns an analysis filtering method of an original digital signal including original samples representing physical quantities, comprising the following steps:
dividing the original signal in order to form plural blocks of samples,
filtering the original samples in a predetermined order and block by block, in order to generate blocks of high and low-frequency samples,
wherein adjacent blocks overlap over a single original sample.
By such method, the buffer memory space required for the filtering is reduced because it is not necessary to store simultaneously all the samples in the buffer memory when filtering the signal block by block and overlap size is minimum. Also, even if overlap size is minimum, a discontinuity between samples over a boundary between blocks is sufficiently suppressed. This is because there is a great difference in the reconstructed signal between overlaps size 0 and 1 but there is not a great difference in the reconstructed signal between overlap size 1 and full overlap in term of the discontinuity (distortion), since such distortion is not reduced in proportion to increase of the size of overlap.